package arithmetic.demo15;

import java.util.List;

/**
 * 动态规划： 分类讨论  + 二维dp表示两个位置 ：回文子串
 */
class Solution {
    public int countSubstrings(String s) {
        // 动态规划的思想

        // 先转化为字符数组好操作
        char[] chs = s.toCharArray();
        int len = chs.length;

        // 创建二维dp 表示两个字符的起始和终止位置
        // i 为起始位置 j 为终止位置
        boolean[][] dp = new boolean[len][len];
        int ret = 0;


        // 开始从下往上填表
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                // 判断首尾是否相等
                if(chs[i] == chs[j]) {
                    // 分情况的相等
                    if(i == j) {
                        // 如果是同一个位置
                        dp[i][j] = true;
                    } else if(i + 1 == j) {
                        // 如果是相邻位置
                        dp[i][j] = true;
                    } else {
                        // 如果中间隔着元素
                        // a b a
                        // a c b c a
                        // 继承中间元素
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 更新结果
                if (dp[i][j]) {
                    ret++;
                }
            }
        }
        return ret;
    }
}

class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countSubstrings("abc"));
    }
}

/**
 * 三目表达式的简化
 */

class Solution2 {
    public int countSubstrings(String s) {
        // 动态规划的思想

        // 先转化为字符数组好操作
        char[] chs = s.toCharArray();
        int len = chs.length;

        // 创建二维dp 表示两个字符的起始和终止位置
        // i 为起始位置 j 为终止位置
        boolean[][] dp = new boolean[len][len];
        int ret = 0;


        // 开始从下往上填表
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                // 判断首尾是否相等
                if(chs[i] == chs[j]) {
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                }

                // 更新结果
                if (dp[i][j]) {
                    ret++;
                }
            }
        }
        return ret;
    }
}

/**
 * 动态规划: 二维dp + 分类讨论 ： 最长回文子串
 */

class Solution3 {
    public String longestPalindrome(String s) {
        // 动态规划思想
        int len = s.length();
        // 创建 dp
        boolean[][] dp = new boolean[len][len];
        // 记录位置
        int begin = 0, end = 0, maxLen = 0;

        //  从下往上填表
        for(int i = len - 1; i >= 0 ; i--) {
            for(int j = i ; j < len; j++) {
                // 判断首尾字符是否相等
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                }

                // 更新最长长度 和记录位置
                if(dp[i][j] && (j - i + 1) >  maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                    end = j;
                }
            }
        }

        // 返回最终结果
        return s.substring(begin, end + 1);
    }
}

/**
 * 动态规划: 二维dp + 分类讨论 + 区间划分 ： 分割回文串（IV）
 */


class Solution4 {
    public boolean checkPartitioning(String s) {
        // 先统计每一个区间的子字符串是否为回文串
        // 动态规划思想查找
        int len = s.length();
        // 创建 二维dp
        boolean[][] dp = new boolean[len][len];

        // 从下往上填表
        for(int i = len - 1 ; i >= 0 ; i--) {
            for(int j = i ; j < len; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    // 判断相同位置，相邻位置，夹中间元素位置
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                }
            }
        }
        // 划分三段区间查找是否为回文串
        for(int j = 1 ; j < len - 1; j++) {
            for(int i = 0 ; i < j ; i++) {
                // 判断三个区间是否为回文子串
                if(dp[0][i] && dp[i + 1][j] && dp[j+1][len-1]) {
                    return true;
                }
            }
        }

        return false;
    }
}

/**
 *  动态规划：二维dp + 分类讨论 + 区间划分 + 单词拆分 ： 分割回文串（II）
 */
class Solution5 {
    public int minCut(String s) {
        // 动态规划思想 + 单词拆分
        int len = s.length();

        // 创建 dp
        boolean[][] dp = new boolean[len][len];

        // 填表
        for(int i = len- 1; i >= 0; i--) {
            for(int j = i ; j < len; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    // 分情况: 相同位置，相邻位置， 夹中间元素位置
                    dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;
                }
            }
        }


        // 进行单词拆分
        // 创建gp
        int[] gp = new int[len];
        gp[0] = 0;


        for(int j = 1; j < len; j++) {
            gp[j] = 0x3f3f3f3f;
            for(int i = 1; i <= j;i++) {
                if(dp[0][j]) {
                    // 先判断整个是否成立
                    gp[j] = 0;
                    break;
                } else if(dp[0][i-1] ) {
                    // 拆分后成立后 更新最小分割次数
                    gp[j] = Math.min(gp[j], gp[i-1] + 1) ;
                }
            }
        }

        return gp[len-1];
    }
}

class Test2 {
    public static void main(String[] args) {
        Solution5 solution5 = new Solution5();
        System.out.println(solution5.minCut("leet"));
    }
}

/**
 * 动态规划： dp + 区间划分 ： 单词划分
 */

class Solution6 {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 使用动态规划的思想
        int len = s.length();

        // 创建dp

        boolean[] dp = new boolean[len];


        // // 特殊情况初始化
        if(wordDict.contains(s.charAt(0) + "")) {
            dp[0] = true;
        }

        for(int i = 0; i < len; i++) {
            for(int j = 1; j <= i ; j++) {
                // 切割出 j 到 i 位置的子字符串
                if(wordDict.contains(s.substring(0,i + 1))) {
                    // 如果整个都包含就置为 true
                    dp[i] = true;
                } else if(wordDict.contains(s.substring(j,i + 1))) {
                    // 如果包含后半部分，继承前半部分的情况
                    dp[i] = dp[j-1];
                    if(dp[i]) break;
                }
            }
        }

        return dp[len-1];
    }
}

/**
 * 题目： 动态规划 + 分类讨论： 最长回文子序列
 */

class Solution7 {
    public int longestPalindromeSubseq(String s) {
        // 动态规划思想 + 分类讨论

        // 创建 dp
        int len = s.length();
        int[][] dp = new int[len][len];

        // 从下往上， 从左往右填表
        for(int i = len - 1; i >= 0; i--) {
            for(int j = i; j < len ; j++) {
                // 首尾相等时
                if(s.charAt(i) == s.charAt(j)) {
                    // 分类讨论
                    if(i == j) {
                        // 自身
                        // 就确定自己为 1 个回文子串
                        dp[i][j] = 1;
                    } else if(i + 1 == j ) {
                        // 相邻
                        // 确定两个长度
                        dp[i][j] = 2;
                    } else if(i + 1 < j){
                        // 中间如果相邻有元素的话
                        // 中间的最长长度 + 自身的两个长度
                        dp[i][j] = dp[i+1][j-1] + 2;
                    }
                } else {
                    // 不相等就继承前面的最长长度
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        // 确定返回值为整个字符串的区间的最大值
        return dp[0][len-1];
    }
}


/**
 * 动态规划： dp + 分类讨论 + 继承前面是最大数据 ： 最长公共子序列
 */

class Solution8 {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(), len2 = text2.length();
        // 创建 dp
        int[][]dp = new int[len1+1][len2 + 1];

        // 初始化
        text1 = " " + text1;
        text2 = " " + text2;
        // 填表
        // 从上往下，从左往右
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    // 如果相等就在前一个位置添上 1
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // 不想等就继承前面最大的
                    dp[i][j] = Math.max(dp[i][j-1] , dp[i-1][j]);
                }
            }
        }
        // 返回值
        // 返回最终一个位置
        return dp[len1][len2];
    }
}


/**
 * 动态规划： dp + 同一区间想等 并且是前往后不相同：不想交的线
 */

class Solution9 {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 动态规划思想
        int len1 = nums1.length, len2 = nums2.length;

        // 创建 dp
        int[][] dp = new int[len1+1][len2+1];

        // 初始化
        // 从上到下 ， 从左到右递增
        for(int i = 1; i <= len1; i++) {
            // 建立下标映射
            for(int j = i ; j <= len2; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    // 如果两个位置想等
                    // 就在前面的基础上 + 1
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    // 如果不想等就继承前面最长的序列
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        // 最终继承 + 迭代的最终位置
        return dp[len1][len2];
    }
}


/**
 * 动态规划： 两个区间dp +  子串对应子序列： 不同的子序列
 */



class Solution10 {
    public int numDistinct(String s, String t) {
        // 动态规划思想
        int tmp = 1000_000_000 + 7;
        int len1 = s.length(), len2= t.length();

        // 创建 dp
        int[][] dp = new int[len1+1][len2+1];

        // 初始化
        for(int i = 0 ; i <= len1; i++) {
//            注意第一行的每一列 ， 也就是每一个子序列的第一个初始化为 1
            dp[i][0] = 1;
        }

        // 自上而下，自左而右填表
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2 ; j++) {
                // 判断尾部是否想等
//                赋值前面的不包含的 子序列的个数
                dp[i][j] = dp[i-1][j];
                if(s.charAt(i-1) == t.charAt(j-1)) {
//                    如果含有就加上这一串
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }

        // 确定最后区间的返回值
        return dp[len1][len2];
    }
}